Digital image processing involves applying changes of some kind to a digital image. One category of image processing is filtering. A “filter” is a process that changes the values pixels in an image based on some criteria. One category of filters is “smoothing” filters. Smoothing filters are generally used to reduce noise and smooth out local image variations. A complement to a smoothing filter is a “sharpening” filter. Sharpening filters are generally used to sharpen and enhance local image variations. Sharpening filters are sometimes implemented using smoothing filters. A smoothing filter is applied to an image. For each pixel, the smoothed value is compared to the original value, and the difference between the smoothed and original pixel is applied in the opposite direction to the original pixel value to obtain a sharpened pixel value. Smoothing filters can also be used for other creative effects, such as, for example, extracting the “texture” of an image. U.S. Pat. No. 6,996,287, entitled “Method and Apparatus for Texture Cloning,” discloses methods of using smoothing filters for extracting texture. Two types of smoothing filters are “Gaussian” filters and “median” filters.
FIG. 1 shows a representation of a simple example image 100 made up of a plurality of pixels 105. Each pixel has a value that defines the color and intensity of that pixel. A pixel value may be a single number, or a set of numbers. A triplet of values, one of each of red, green, and blue components (“channels”), is sometimes used. In FIG. 1, a simple, single value is used, ranging from 1 to 16. The values of some of the pixels in the top left corner of image 100 are shown in FIG. 1.
Gaussian and median filters typically modify each pixel in an image by replacing the original value of the pixel with a modified value based on the values of pixels contained in a neighborhood (“kernal”) around the pixel in question. A common shape of a neighborhood is a square, though other shapes are sometimes used. The size of the neighborhood is a variable parameter chosen by a user. The parameter is often referred to as the “radius” of the filter, even though the neighborhood is commonly not circular and therefore strictly speaking does not have a radius.
A Gaussian filter replaces the value of a pixel with a weighted average of the pixels in a neighborhood around the pixel, with closer pixels weighted more heavily than more distant pixels according to a Gaussian distribution. A Median filter replaces the value of a pixel with the median value of the pixels in a neighborhood of the pixel.
FIG. 1 shows an example of a square neighborhood 130 of an example pixel 120. Neighborhood 130 extends four pixels in each vertical and horizontal direction from pixel 120. Its “radius” is therefore by convention deemed to be four. Each side of neighborhood 130 is nine pixels in length, and the total number of pixels in the neighborhood is 81. In the general case of a square neighborhood of radius r, each side of the neighborhood is 2r+1 pixels in length, and the number of pixels in the neighborhood is (2r+1)2.
In the example of FIG. 1, values in a range of 1 to 16 are shown for each of the 81 pixels in neighborhood 130. Several methods can be used to determine the median value of the pixels in neighborhood 130. One method is to arrange all the pixel values in order from lowest to highest, and to then identify the value of the pixel for which an equal number of pixels have a higher or lower value.
Another method is to construct a histogram of the pixel values in neighborhood 130. In the embodiment of FIG. 1, there are 16 possible pixel values, namely the whole numbers from 1 to 16. A histogram for the image of FIG. 1 will therefore have 16 elements, or “buckets,” one for each possible pixel value. The histogram for neighborhood 130 may be constructed by sequentially traversing the pixels in neighborhood 130, determining the value of each pixel, incrementing the histogram “bucket” for that value by one, and then moving onto the next pixel. Table 1 shows the resulting histogram for neighborhood 130 of FIG. 1.
TABLE 1Histogram for Neighborhood 130 of FIG. 1PixelNumber ofValuePixels11121530435126970829010011012013214515121610
The median is found by adding the number of pixels for each of the elements (“buckets”) of the histogram, from lowest pixel value (i.e. 1) to highest, until the sum is greater than or equal to n/2+1, where n is the number of pixels in the neighborhood (i.e. [(2r+1)2/2+1] with r=4, or 41, for neighborhood 130). Using the histogram numbers from Table 1, the first element for which the sum of the number of pixel in successive elements is greater than or equal to 41 is element “5” (11+15+0+3+12=41). The median value of the pixels in neighborhood 130 is therefore “5”. Accordingly, in applying a median filter of radius 4 to the image of FIG. 1, the original value of “16” for pixel value 120 is replaced with the median value “5” of neighborhood 130. FIG. 2 shows the filtered image 200 that is constructed by applying a median filter of radius 4 to image 100 of FIG. 1. In FIG. 2, the original value of “16” for pixel 120 has been replaced with the filtered, median value “5.” To complete filtered image 200, filtered pixel values must be determined for the remaining pixels in FIG. 100.
FIG. 3 shows the neighborhood 330 that is used to determine the filtered value for pixel 320, which is the next pixel adjacent to pixel 120 in a vertically downwards direction. The terms “vertical” and “horizontal” are used herein as a convenient way to refer to direction in the images in the drawing figures, Those of skill in the art will understand that an image can be oriented any way, so that “vertical” and “horizontal” do not refer to absolute directions, but serve as a means to differentiate between vertical “columns” and horizontal “rows” of pixels in a raster image.
To determine the filtered value for pixel 320, a histogram for neighborhood 330 can be constructed in the same manner the histogram of Table 1 was constructed for neighborhood 130 of pixel 120 in FIG. 1. Table 2 shows the resulting histogram for neighborhood 330 of FIG. 2.
TABLE 2Histogram for Neighborhood 330 of FIG. 3PixelNumber ofValuePixels11021930425136970829010011012013114415111610
Sequentially adding the numbers for each element in the histogram of Table 3 until the sum is equal to or greater than 41 again ends at the element corresponding to pixel value “5” (10+19+0+2+13=44). Accordingly, the median filtered value for pixel 320 is “5.” FIG. 4 shows this new value for pixel 320 added to the filtered image 200 of Figure
Filtered values for the remaining pixels in FIG. 100 can be found in a similar manner as that used to find the filtered values for pixels 120 and 320. That is, the corresponding neighborhood is found, the histogram for the neighborhood is constructed by traversing each pixel in the neighborhood, incrementing the appropriate element of the histogram for each pixel value, and then the histogram is traversed until the sum of histogram elements is greater or equal to 41 (i.e. [(2r+1)2/2+1]). In this process, constructing the histogram for each pixel can be time consuming, requiring a separate operation (namely incrementing the appropriate histogram element) for each pixel in each pixel's respective neighborhood. Because the number of pixels in a square neighborhood of radius r is (2r+1)2, the time required to per pixel to construct the corresponding histogram is of the order of r2. As r gets large (e.g. on the order of 100 or more), the time to construct the histogram, and therefore apply a median filter, becomes unsatisfactorily large.
Fortunately, the distributive property of histograms allows the average time per pixel to be reduced somewhat. The distributive property of histograms is that for any two disjoint (i.e. non-overlapping) regions A and B, the histogram of the union of those two regions is the sum of the histograms for each region. Anotherwords, if HA is the histogram for region A and HB is the histogram for region B, the histogram for the combination of A+B is HA+HB. Similarly, if a region is the result of removing a region B from region A, the histogram for the resulting region A−B is HA−HB.
In FIG. 3, neighborhood 130 is shown in dotted outline. Comparing neighborhoods 130 and 330, it can be seen that for the most part, the two neighborhoods overlap. The difference between neighborhood 330 and neighborhood 130 is that neighborhood 330 does not include the top row 340 of neighborhood 130, and includes an extra row 350 (i.e. the bottom row of neighborhood 330) that is not included in neighborhood 130
Using the convention that H130 is the histogram for neighborhood 130, H330 the histogram for neighborhood 330, H340 the histogram for row 340, and H350 the histogram for neighborhood 350, using the distributive property of histograms, H330=H130−H340+H350. Accordingly, once the histogram for neighborhood 130 of pixel 120 has been created, the histogram for the neighborhood 330 of pixel 320 can be calculated using the existing histogram H130 for neighborhood 130 and the two small histograms H340 and H350 for rows 340 and 350, respectively. Because rows 340 and 350 have fewer pixels than neighborhood 330, determining their respective histograms will take fewer operations than determining he histogram for neighborhood 330 from scratch. The number of pixels in rows 340 and 350, collectively, is 2(2r+1)=4r+2. Accordingly, by using the distributive property of histograms, the number of average operations per pixel required to create the histogram for a neighborhood of radius r for that pixel is on the order of r, instead of on the order of r2, a substantial reduction. FIG. 5 illustrates graphically how the histogram for neighborhood 330 is derived from the histograms for neighborhood 130 and rows 340 and 350, respectively
In FIG. 5, each histogram is simply represented as a row of 16 boxes, one for each pixel value from 1 to 16, with the box for pixel value “1” being the leftmost box and the box for pixel value “16” being the rightmost box. As shown in FIG. 5, for each pixel value box, if one starts with the value for H130, subtracts the value for H340, and adds the value for H350, the result is the value for H330. For example, using the box for the pixel value “1” as an example (i.e. the left-most box in each histogram), the value for H330 is 11−2+1=10.
A further optimization for deriving histograms of pixel values in neighborhoods of radius r for adjacent pixels in an image is disclosed in U.S. Pat. No. 7,010,163 entitled “Method and Apparatus for Processing Image Data,” issued Mar. 7, 2006 (the '163 patent), assigned to the assignee of the present invention, and incorporated by reference in its entirety herein. The method disclosed in the '163 patent is based on the observation that in addition to there being overlap in the neighborhoods of pixels adjacent to each other in the vertical direction, there is also overlap in the horizontal direction. Accordingly, additional optimization can be obtained by simultaneously deriving histograms for several horizontally adjacent pixels at a time.
FIG. 6 shows an example of the method disclosed in the '163 patent for simultaneously deriving histograms for the neighborhoods for four horizontally adjacent pixels 120, 610, 620 and 630. The corresponding neighborhoods for pixels 120, 610, 620, and 630 are overlapping neighborhoods 130, 615, 625 and 635, respectively. A “sideview” representation of neighborhoods 130, 615, 625 and 635 is shown below image 100 in FIG. 6 to more clearly show how the neighborhoods overlap. In the example of FIG. 6, the neighborhoods are again square neighborhoods of radius 4. The area of overlap is shaded overlap region 650 shown in FIG. 6.
Overlap region 650 is a region that is common to each of neighborhoods 130, 615, 625, and 635. In the embodiment of FIG. 6, overlap region 650 is nine pixels high and six pixels wide. In the more general case, for “r” being the radius of the neighborhood and “N” being the number of horizontally adjacent pixels for which histograms are being simultaneously derived, the height of region 650 is the full vertical dimension of the neighborhood (i.e. 2r+1), while its width is 2r+2−N. There is no overlap if N is greater than or equal to 2r+2. The maximum number for N for which there is any overlap is therefore 2r+1.
FIG. 7 shows separate “top” views of each of neighborhoods 130, 615, 625, and 635 of FIG. 6. As shown in FIG. 7, each neighborhood can be viewed as the combination of overlap region 650 and one or two other additional regions. For example, neighborhood 130 is the combination of overlap region 650 and additional region 710. Neighborhood 615 is the combination of overlap region 650 and additional regions 720a and 720b (which can be considered a non-contiguous additional region 720). Neighborhood 625 is the combination of overlap region 650 and additional regions 730a and 730b (which can be considered a non-contiguous additional region 730). Neighborhood 635 is the combination of overlap region 650 and region 635. It will be noted that the width of each of additional regions 710, 720, 730 and 740 is the same: three pixels in the embodiment FIG. 7 in which the radius r is 4 and the number of simultaneously calculated histograms N is 4. In the more general case, the width of each additional region is N−1.
Using the distributive property of histograms, the histogram for each of neighborhoods 130, 615, 625 and 635 can be derived from the histogram for overlap region 650 and the histograms for each of additional regions 710, 720, 730 and 740 (which can be referred to as “partial histograms”) as follows:H130=H650+H710 H615=H650+H720 H625=H650+H730 H635=H650+H740 The filtered value for pixels 120, 610, 620 and 630 can then be found by finding the median value of the corresponding histograms H130, H615, H625 and H635, as described above.
Once the initial partial histograms H650, H710, H720, H730 and H740 have been derived, the histograms for the pixels immediately below pixels 120, 610, 620 and 630 can be found using a process similar to that described with respect to FIG. 3. In that manner, four columns of pixels can be traversed using the method used for traversing a single column in the embodiment of FIG. 3, leading to increased efficiency versus using the method of FIG. 3 to traverse on column at a time.
Although it takes more operations to set up the original histograms, that only occurs once per column. Because of the large number of pixels in each column in a typical image being processed, the processing time is dominated by the average time it takes to process each additional pixel after the original histograms have been derived.
It will be recalled that in the embodiment of FIG. 3, deriving a histogram for the next pixel in a column required adding a new 2r+1 wide row of pixels to the existing histogram and subtracting the top 2r+1 wide row of pixels from the histogram. Because the adding and subtracting steps are essentially inverses of each other that require the same number of operations, processing times between histogram derivation processes can be compared by comparing the average number of operations needed to either add or subtract a row of pixels from a histogram.
In the embodiment of FIG. 7, adding a row of pixels to each of histograms H130, H615, H625 and H635. is accomplished by adding partial rows of pixels to each of partial histograms H650, H710, H720, H730 and H740. FIG. 8 shows the various partial rows of pixels that are added to each of histograms H650, H710, H720, H730 and H740. As shown in FIG. 8, six-pixel wide row 850 is added to the histogram for region 650 (H650). Three pixel wide row 810 is added to the histogram for region 710 (H710). Two pixel wide row 820a and single pixel 820b are added to the histogram for region 720 (H720). Single pixel 830a and two pixel wide row 830b are added to the histogram for region 730 (H730). Three pixel wide row 840 is added to the histogram for region 740 (H740). The adding of a pixel to a histogram is a single operation. Thus, to add a row of pixels to the set of four histograms H130, H615, H625 and H635 requires a total of 18 operations (i.e. histogram adjustments): six for histogram H650, and three for each of histograms H710, H720, H730 and H740. The average number of histogram adjustments per pixel being processed thus is 18/4=4.5, compared to 9 histogram adjustments per pixel for the embodiment of FIG. 3. In the more general case for radius r and N number of simultaneous columns, the average number of histogram adjustments A per pixel is:A=[(2r+2−N)+N(N−1)]/N=(2r+2)/N+N−2For a fixed r, solving for minimum A yields N=SQRT(2r+2). Using this value of N for the equation for A yields A=2SQRT(2r+2)−2 (for adding a row of pixels to a histogram) or A=4SQRT(2r+2)−4 (for doing a complete histogram adjustment comprising adding a row to the bottom and subtracting a row from the top). Accordingly, the process of FIGS. 6 through 8 has a computational cost on the order of SQRT(r), compared to the order of r for the process of FIG. 3, and the order of r2 for the basic one histogram per pixel process.
For sufficiently large values of r and N, the '163 patent discloses a further optimization, which is illustrated in FIG. 9. FIG. 9 shows a “side” view of N neighborhoods 900 of N horizontally adjacent pixels 905 with radius r. In the example of FIG. 9, r=13, and N=14. As shown in FIG. 9, in this embodiment, each neighborhood consists of a fully overlapping region 910, a partially overlapping region 920 or 930, and a remaining region 940. Accordingly, the histogram for each neighborhood 900 can be derived by adding three histograms: namely the histogram for fully overlapping region 910, the histogram of either partially overlapping region 920 or 930, and the histogram of remaining region 940. In the embodiment of FIG. 9, there is one overlapping region 910 that is 2r+2−N pixels wide, there are two partially overlapping regions 920 and 930 that are N/2 pixels wide, and there are N remaining regions 940. The number of histogram adjustments to move one pixel downwards is therefore:A=[(2r+2−N)+2(N/2)+N(N/2−1)]/N=(2r+2)/N+N/2−1
FIG. 10 shows an alternative arrangement of overlapping region 1010 and partially overlapping regions 1020, 1030 (comprised of regions 1030a and 1030b), and 1040 (comprised of regions 1040a and 1040b) using the method disclosed in the '163 patent.
As will be appreciated by those skilled in the art, the increasing performance from the methods illustrated in FIGS. 3 to 10 comes from deriving methods to take advantage as much as possible of the overlap among neighborhoods of groups of adjacent pixels in an image. Because the resolution and color depth (i.e. the number of bits per pixel) of typical images continues to increase, there continues to be a need for alternative methods to optimize the calculation of histograms for neighborhoods of pixels in an image, both for purposes of applying median filtering to an image and for other image processing purposes.